package practice;

import java.util.HashMap;
import java.util.Map;

/**
 * @Description: https://leetcode.cn/problems/lru-cache/
 * @Author Ammar
 * @Create 2023/7/21 20:24
 */
public class _146_LRU缓存机制 {
    private Map<Integer, Node> map;
    private Node first;
    private Node last;

    private int capacity;


    public _146_LRU缓存机制(int capacity) {
        map = new HashMap<>();
        this.capacity = capacity;
        first = new Node();
        last = new Node();
        first.next = last;
        last.prev = first;
    }


    public int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;
        remove(node);
        addFirst(node);
        return node.value;
    }

    private void addFirst(Node node) {
        node.next = first.next;
        first.next.prev = node;
        first.next = node;
        node.prev = first;
    }

    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) {
            node.value = value;
            remove(node);
        } else {
            if (map.size() == capacity) {
                remove(map.remove(last.prev.key));
            }
            map.put(key, node = new Node(key, value));
        }
        addFirst(node);
    }


    private static class Node {
        int key;
        int value;
        Node prev;
        Node next;

        public Node() {
        }

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
}
